package thinking.backtracking;

/**
 * 假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。
 * 棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。
 * 每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。
 * 我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
 *
 * @author yeyangtao created at 15:36 2020/10/30
 */
public class MinDistBT {
    private int minDist = Integer.MAX_VALUE;

    /**
     * 调用方式：minDistBacktracking(0, 0, 0, w, n);
     *
     * @param i    行
     * @param j    列
     * @param dist 当前路径长度
     * @param w    矩阵
     * @param n    矩阵 n*n
     */
    public void minDistBacktracking(int i, int j, int dist, int[][] w, int n) {
        //到达n-1,n-1这个位置
        if (i == n && j == n) {
            if (dist < minDist) minDist = dist;
            return;
        }
        //往下走
        if (i < n) {
            minDistBacktracking(i + 1, j, dist + w[i][j], w, n);
        }
        //往右走
        if (j < n) {
            minDistBacktracking(i, j + 1, dist + w[i][j], w, n);
        }
    }
}
